#pragma once
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<numeric>
#include<stack>
#include<queue>
using namespace std;

class Solution {
public:
    string compressString(string S) {
        string ans;
        int i = 0, j = 0, n = S.size();
        while (i < n)
        {
            while (j < n - 1 && S[j] == S[j + 1])
            {
                ++j;
            }
            ans += S[i];
            int len = j - i + 1;
            ans += to_string(len);
            i = j + 1;
            j = i;
        }
        return ans.size() >= S.size() ? S : ans;
    }

    bool canJump(vector<int>& nums) {
        int rightMost = 0;
        for (int i = 0; i < nums.size(); ++i)
        {
            if (i <= rightMost)
            {
                rightMost = max(rightMost, i + nums[i]);
                if (rightMost >= nums.size() - 1) return true;
            }
            else return false;
        }
        return false;
    }

    int longestValidParentheses(string s) {
        int ans = 0;
        stack<int> st;
        st.push(-1);
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(')
                st.push(i);
            else {
                st.pop();
                if (st.empty()) st.push(i);
                else ans = max(ans, i - st.top());
            }
        }
        return ans;
    }

    int findDuplicate(vector<int>& nums) {
        int n = nums.size();
        int left = 0, right = n - 1;
        while (left < right)
        {
            int mid = (left + right) >> 1;
            int cnt = 0;
            for (int i = 0; i < n; ++i)
                cnt += nums[i] <= mid;
            if (cnt <= mid)
                left = mid + 1;
            else
                right = mid;
        }
        return right;
    }

    int minChanges(int n, int k) {
        if (n < k) return -1;
        int ans = 0;
        while (n)
        {
            if (n % 2 == 0 && k % 2 == 1) return -1;
            else if (n % 2 == 1 && k % 2 == 0) ++ans;
            n /= 2;
            k /= 2;
        }
        return ans;
    }

    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(), n = text2.size();
        vector<int> dp(n + 1);
        for (int i = 0; i < m; ++i)
        {
            int pre = dp[0];
            for (int j = 0; j < n; ++j)
            {
                int tmp = dp[j + 1];
                dp[j + 1] = text1[i] == text2[j] ? pre + 1 : max(dp[j + 1], dp[j]);
                pre = tmp;
            }
        }
        return dp[n];
    }

    int _minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int j = 0; j <= n; ++j)
            dp[0][j] = j;
        for (int i = 0; i < m; ++i)
        {
            dp[i + 1][0] = i + 1;
            for (int j = 0; j < n; ++j)
            {
                if (word1[i] == word2[j])
                    dp[i + 1][j + 1] = dp[i][j];
                else
                    dp[i + 1][j + 1] = min(min(dp[i + 1][j], dp[i][j + 1]), dp[i][j]) + 1;
            }
        }
        return dp[m][n];
    }

    int __minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        vector<vector<int>> memo(m, vector<int>(n, -1));
        auto dfs = [&](auto&& dfs, int i, int j)->int
        {
            if (i < 0) return j + 1;
            if (j < 0) return i + 1;
            int& res = memo[i][j];
            if (res != -1) return res;
            if (word1[i] == word2[j]) return res = dfs(dfs, i - 1, j - 1);
            return res = min(min(dfs(dfs, i - 1, j), dfs(dfs, i, j - 1)), dfs(dfs, i - 1, j - 1)) + 1;
        };
        return dfs(dfs, m - 1, n - 1);
    }

    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        vector<int> dp(n + 1);
        iota(dp.begin(), dp.end(), 0);
        for (int i = 0; i < m; ++i)
        {
            int pre = dp[0];
            dp[0] = i + 1;
            for (int j = 0; j < n; ++j)
            {
                int tmp = dp[j + 1];
                dp[j + 1] = word1[i] == word2[j] ? pre : min(min(dp[j], dp[j + 1]), pre) + 1;
                pre = tmp;
            }
        }
        return dp[n];
    }
    
    struct KVcom
    {
        bool operator()(const pair<int, int>& p1, const pair<int, int>& p2)
        {
            return p1.first < p2.first||(p1.first==p2.first&&p1.second > p2.second);
        }
    };

    void chika(vector<vector<int>> nums,int k)
    {
        priority_queue<pair<int, int>,vector<pair<int,int>>,KVcom> heap;


        for (int i = 0; i < nums[0].size(); ++i)
        {
            heap.emplace(nums[0][i],nums[1][i]);
        }
        int s = 0, t = 0;
        while (k--)
        {
            s += heap.top().first;
            t += heap.top().second;
            heap.pop();
        }
        cout << s << t;
    }
};
